package 并查集;

public class 并查集 {
	
	public static void main(String[] args) {
		//并查集主要用来判断 图 中，是否存在环（通路），集合是否相交
		//从图的边开始入手，将顶点一个一个连接成树（有根和子结点，用于查找是否同根），然后判断
		//两顶点是否同根，不同，则连接两集合（两树），同根，则连通
		
		//初始化顶点之间关系，和层高
		int pertent[] = new int[VERTICES];
		int rank[] = new int[VERTICES];
		initialise(pertent, rank);
		
		//图的边，一共6条，每一条连接两顶点
		int edges[][] = {
				//去掉{2,4}后无环
				{0,1},{1,2},{1,3},
				{2,4},{3,4},{2,5}
		};
		//合并
		for(int i = 0; i < edges.length; i++) {
			//找到每一条边的两个顶点
			int x = edges[i][0];
			int y = edges[i][1];
			//合并
			if(union_vertices(x, y, pertent, rank) == 0) {
				System.out.println("有环！");
				return;
			}
		}
		System.out.println("无环！");
	}
	
	//顶点数量
	final static int VERTICES = 6;
	
	/**
	 * 初始化顶点之间关系，默认-1，没有关系
	 * @param pertent 数组用来表示顶点之间关系，下标为顶点，值为该顶点父顶点
	 * @param rank 代表层高，默认0
	 */
	public static void initialise(int pertent[], int rank[]) {
		for(int i = 0; i < VERTICES; i++) {
			pertent[i] = -1;
			rank[i] = 0;
		}
	}
	
	/**
	 * 查找根节点
	 * @param x 查找此节点的根节点
	 * @param pertent 顶点之间关系数组
	 * @return
	 */
	public static int find_root(int x, int pertent[]) {
		//根节点没有父结点，所以pertent数组中只要是-1的就找到了，单独一个节点也可以是根节点
		int x_root = x;
		//如果此结点不是-1，说明它有父结点，就找它的父节点
		while(pertent[x_root] != -1) {
			//该结点的值，代表它父结点的下标，就去找下标
			x_root = pertent[x_root];
		}
		return x_root;
	}
	
	/**
	 * 合并两树（集合），其实合并操作是在查找操作之前执行，因为一开始都是单独的顶点，都是根
	 * 所以才要合并这两个顶点，然后创造出pertent数组
	 * @param x 一个顶点
	 * @param y 另一个顶点
	 * @param pertent 顶点之间关系数组
	 * @param rank 添加表示层高数组
	 * @return 0 代表失败，1 代表成功
	 */
	public static int union_vertices(int x, int y, int pertent[], int rank[]) {
		//查找两顶点的根
		int x_root = find_root(x, pertent);
		int y_root = find_root(y, pertent);
		//如果是同根则不合并
		if(x_root == y_root) {
			//失败
			return 0;
		}else {
			//成功，将x放到y下（少连多）
			//1.就是在这时，pertent数组才慢慢创建，值代表此结点父结点是谁
			//2.不要将x或y放到值里，因为x或y可能在最底层，如果连接上，会导致路径很长（树高）
			//pertent[x_root] = y_root;
			
			//路径压缩，将层低的那个放到层高的那个下面
			if(rank[x_root] > rank[y_root]) {
				//x 更高，将 y 的父结点改为 x
				pertent[y_root] = x_root;
				
			}else if(rank[y_root] > rank[x_root]) {
				//y 更高，将 x 的父结点改为 y
				pertent[x_root] = y_root;
				
			}else {
				//x y 相同，任意合并，将父结点层高加一
				pertent[x_root] = y_root;
				rank[y_root]++;
			}
			return 1;
		}
	}
}
